In wireless and wireline applications, particularly those with significant intersymbol interference, error detection and correction is performed using convolutional encoding and Viterbi Decoding. Convolutional encoding is performed by convolving a data input bit to hardware or software encoder with one or more previous input bits. An example of a conventional IS-95 rate 1/2, constraint length 9 convolutional encoder 10 is shown in FIG. 1a. The information bits are input to a series of delay elements 12 such as a shift register that is tapped at various points. The tapped values are combined by an XOR function 14 to generate encoded data symbols. In the example encoder 10, two output bits, c.sub.0 and c.sub.1, are generated for every input bit. Thus, this encoder has a rate of 1/2. The constraint length represents the total span of values used by the encoder and is represented by the symbol K. A constraint length K=9 means that there are 2.sup.(9-1) =256 encoder states (since the ninth bit is the input bit). These states are designated represented as state S.sub.0 (decimal 0, binary 00000000) to state S.sub.255 (decimal 255, binary 11111111).
FIG. 1b illustrates a typical application environment using convolutional encoding and Viterbi decoding. Source data 5 is input to convolutional encoder 10. Encoded data is output as a sequence of data symbols 20 which are formatted appropriately and transmitted over a communications link 22. The communications link 22 introduces noise into the data signal and therefore the transmitted data symbols may be corrupted by the time they reach their destination. Each received (and possibly corrupted) data symbol 24 is processed by a convolutional decoder 26 to generate decoded data 28 which corresponds to the most likely sequence of source data 5.
The received data signals 24 are processed according to the Viterbi algorithm. The basis of the Viterbi algorithm is to decode the convolutionally encoded data symbols by using knowledge of the possible encoder state transitions from one given state to the next based on the dependance of a given data state on past data. The allowable state transitions are typically represented by a trellis diagram. The Viterbi algorithm provides a method for minimizing the number of state paths through the trellis by limiting the paths to those with the highest probability of matching the transmitted data sequence based on the received sequence.
FIG. 2 is an illustration of the basic Viterbi algorithm butterfly computation. Four possible encoder transitions from a present state (PS) to a next state (NS) are illustrated, where the present state is equivalent to the numeric value of the data stored in the K-1 delay elements 12 of the encoder 10. When a bit is input to the encoder, the binary value is shifted to the right and the input bit is moved into the most significant bit position (shown in bold in the next state). As illustrated, NS.sub.0 can be reached with a 0 input bit from either PS.sub.0 or PS.sub.1. Similarly, NS.sub.128 can be reached with a 1 input bit from either PS.sub.0 or PS.sub.1. The Viterbi algorithm provides a process by which the most likely of the two possible transition paths can be determined and subsequently selected as the "survivor" path. Once a sequence of survivor paths has been determined, the most probable data input sequence can be reconstructed, thus decoding the convolutionally encoded data.
This determination consists of three basic steps. In the first step, the received data symbol, typically an 8 or 16 bit digital value representing the magnitude of voltage or current of an input signal, is processed to determine the Euclidean distance between the received data symbol and all possible actual data symbols, uncorrupted by noise, which could result from a state transition from the present to a next state. This is known as a branch metric computation, the results of which are stored in memory for use during the next step. The branch metric computation provides a measurement of the likelihood that a given path from a present state to a next state is correct. The branch metric m for a transition from present state i to next state j at instant k may be represented as: ##EQU1## where x.sub.n (k) is the received nth data symbol, C.sub.n,ij is the actual data symbol which would result from state transition of i to j in the absence of any transmission noise and is determined from the structure of the convolutional encoder, and the rate is 1/R. For a rate 1/R encoder, there are two possible encoder state transitions and therefore two branch metrics must be computed for each next state. Only the relative magnitudes of various branch metrics are important in Viterbi decoding. Since the same input data symbol is processed in each branch metric, the term .SIGMA.x.sub.n.sup.2 is the same for all states i and j and can therefore be removed. Further, .SIGMA.c.sub.n,ij.sup.2 is constant if a polar representation is used (i.e., a value of c.sub.n,ij =0 or 1 corresponds to -1 or +1 respectively). Removing these terms (and the leading -2 scaler value) results in a reduced Euclidean branch metric of: ##EQU2## Thus, decoding data signals from a convolutional decoder of rate 1/R with a constraint length of K requires determining a total of 2.sup.K metrics values for each data input symbol. As used herein, the set of 2.sup.K metrics values is defined as the complete branch metric set for a particular data input symbol.
One important property of a class of convolutional encoders commonly used is that the second half of the branch metric values are negatives of the first half. Thus, in FIG. 2, m.sub.0,128 =-m.sub.0,0 and m.sub.1,128 =-m.sub.0,128. Therefore, only half of the branch metric set for a given data input symbol must be explicitly calculated by the decoder during Viterbi decoding.
In the second step, the previously stored branch metric values for all possible state transitions are processed to determine an "accumulated distance" for each input path. The path with the minimum distance (i.e., maximum probability) is then selected as the survivor path. This step is known as Add-Compare-Select, or ACS. The ACS operation can be broken into two operations: (1) the Add operation, or path metric computation, and (2) the Compare-Select operation. The path metric Add operation is the accumulation of the present state cost (a value initialized by the user at the start of the Viterbi processing) with the branch metric values for a received data input symbol. As shown in FIG. 2, the two path metric operations for next state 00000000 are: EQU PS.sub.0 +m.sub.0,0 and PS.sub.1 +m.sub.1,0 (Equ. 3)
The path metric operations for next state 10000000, since the second half metrics are the inverse of the first half, can be written as: EQU PS.sub.0 -m.sub.0,0 and PS.sub.1 -m.sub.1,0 (Equ. 4)
The decoder computes and compares two values from the Add operation to determine the minimum (or maximum, depending on implementation) and stores one or more "traceback bits" to indicate the selected survivor path.
The third step is known as traceback. This step traces the maximum likelihood path through the trellis of state transitions, as determined by the first two steps, and reconstructs the most likely path through the trellis to extract the original data input to the encoder. In this example, the survivor path is represented by the least significant bit of the present state, i.e., the traceback bit (shown in bold in FIG. 2). For example, if the path from present state S.sub.1 is chosen over the path from present state S.sub.0, the traceback bit is 1. Various methods of processing traceback data to determine the original data input to the encoder are well known to those skilled in the art.
Because Viterbi decoding is so prevalent in digital signal processing applications, it is important that the convolutional decoder be able to process the Viterbi algorithm quickly and efficiently. Conventional implementations comprise a programmable digital signal processor and a decoder algorithm that computes all 2.sup.K metrics for a given data input symbol 24 at the start of a decoding process and stores the entire branch metric set in memory. However, this brute force technique requires a minimum of 2.sup.K calculations and thus can consume a comparatively large number of machine cycles. Further, storing the entire table can consume a relatively large amount of memory. Although conventional techniques achieve some reduction by storing only the first half of the branch metric values, since the second half is simply the inverse of the first half, there is still a great deal of redundancy in the metric data, resulting in a waste of storage area.
According to the present invention, efficient branch metric computation for a Viterbi convolutional decoder is provided by processing a received data symbol to generate a reduced set of branch metrics for an encoder of constraint length K, instead of the entire set of 2.sup.K metrics, and storing the reduced set in memory for use in the Viterbi processing. The reduced metric set comprises a kernel of the unique metric values for a present data input symbol which exist in the complete metric set and may also include a small subset of precalculated metric values from the complete set. A sequence of K basic data transformations is defined according to the physical structure of the convolutional encoder and used to eliminate redundances in the complete metric set. By applying these transformations to the kernel metric values, all 2.sup.K metrics can be extrapolated.
The reduced metric sequence for a data input symbol is stored in memory as one or more reduced base sets of metric values and a sequence of base set and polarity associations used during the add-compare-select (ACS) step of Viterbi processing. During the ACS operation, the branch metric value required for each state calculation is retrieved from the associated base set and a particular set of path metric operation is chosen or the sign of the retrieved branch metric value is calibrated according the to the associated polarity. This method of reducing the number of branch metrics which must be calculated and stored for each data input symbol results in a substantial savings in the number of cycles required to calculate the complete branch metric set as well as in the amount of storage required to store the predefined branch metric values.